package B刷题.B链表问题;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：在单链表和双链表中删除倒数第K个节点
 * @date 2022/12/12 16:29
 */
public class Code02_在单链表和双链表中删除倒数第K个节点 {

    /**
     * 思路：
     * 找到删除节点的前一个节点，将该节点的下一个节点指向下下个节点；
     * 注意删除节点是头节点的特殊情况；
     */
    public static Node removeLastKthNode(Node head, int k) {
        // 计算链表长度
        int length = 0;
        Node cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        // 长度为0、长度小于k，返回
        if (length == 0 || length < k) {
            return head;
        }
        // 删除的是第一个
        if (length == k) {
            return head.next;
        }
        // 删除的节点索引位
        int delIndex = length - k + 1;
        // 当前到的节点索引位
        int i = 1;
        cur = head;
        while (i <= delIndex - 2) {
            cur = cur.next;
            i++;
        }
        cur.next = cur.next.next;
        return head;
    }

    /**
     * 思路：
     * 找到删除节点的前一个节点，将该节点的下一个节点指向下下个节点，下下个节点的上一个节点指向该节点；
     * 注意删除节点是头节点的特殊情况；
     */
    public static DoubleNode removeLastKthNode(DoubleNode head, int k) {
        // 计算链表长度
        int length = 0;
        DoubleNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        // 长度为0、长度小于k，返回
        if (length == 0 || length < k) {
            return head;
        }
        // 删除的是第一个
        if (length == k) {
            if (head.next!=null){
                head.next.last=null;
            }
            return head.next;
        }
        // 删除的节点索引位
        int delIndex=length-k+1;
        cur=head;
        int i=1;
        // 删除的节点前一个节点与后一个节点改变指向
        while (i<=delIndex-2){
            cur=cur.next;
            i++;
        }
        cur.next=cur.next.next;
        if (cur.next.next!=null){
            cur.next.next.last=cur;
        }
        return head;
    }

}
